class Graph<T> {
    // 顶点
    private vertices: T[] = [];
    // 边: 邻接表 Map 类型的特性,key只有一个，一个key可以有多个value，而且value不重复
    private adjList: Map<T,T[]> = new Map();
    
    // 添加顶点和边的方法
    addVertex(vertex:T){
        // 将顶点添加到数组中保存
        this.vertices.push(vertex);
        // 创建一个邻接表中的数组
        this.adjList.set(vertex,[])
    }
    addEdge(v1:T,v2:T){
        // 因为是无向图，所以要相互push
        this.adjList.get(v1)?.push(v2);
        this.adjList.get(v2)?.push(v1);
    }

    //打印
    traverse(){
        console.log('Graph:')
        this.vertices.forEach(vertex=>{
            const edges = this.adjList.get(vertex);

            console.log(`${vertex} -> ${edges?.join(' ')}`)
        })
    }

    // 广度优先遍历
    bfs(){
        // 1、判断是否有顶点
        if(this.vertices.length === 0) return;

        // 2、创建队列结构访问每一个顶点
        const queue:T[] = [];
        queue.push(this.vertices[0])

        // 3、创建Set结构，记录某一个顶点是否被访问过
        const visited = new Set<T>();
        visited.add(this.vertices[0])

        // 4、遍历队列中的每一个顶点
        while(queue.length){
            const vertex = queue.shift()!;
            console.log(vertex);

            //相邻的顶点
            const neighbors = this.adjList.get(vertex);
        
            if (!neighbors) continue;
            // 遍历所有的相邻节点，将其加入到队列
            for (const nei of neighbors){
                // 已经加入过的不再加入
                if(!visited.has(nei)){
                    visited.add(nei);
                    queue.push(nei);
                }
            }
        }
    }


}

const graph = new Graph();

graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');
graph.addVertex('G');
graph.addVertex('H');
graph.addVertex('I');

graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');

graph.traverse()

graph.bfs()

export default {}